import java.util.*;
public class test {
    // leetcode 56.合并区间
    public int[][] merge(int[][] intervals) {
        Stack<int[]> stack = new Stack<>();
        int n = intervals.length;
        Arrays.sort(intervals,Comparator.comparing(a -> a[0]));
        int[] temp = intervals[0];
        stack.add(temp);
        for(int i = 1;i < n;i++){
            int start1 = temp[0];
            int end1 = temp[1];
            int start2 = intervals[i][0];
            int end2 = intervals[i][1];
            if(end1 >= start2){
                stack.pop();
                temp = new int[]{start1,end1 > end2 ? end1 : end2};
            }else {
                temp = intervals[i];
            }
            stack.add(temp);
        }
        n = stack.size();
        int[][] l = new int[n][2];
        for(int i = 0;i < n;i++){
            l[i] = stack.pop();
        }
        return l;
    }
    // leetcode 435.无重叠区间
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals,Comparator.comparing(a -> a[0]));
        int num = 0;
        int right = intervals[0][1];
        for(int i = 1;i < n;i++){
            if(right > intervals[i][0]){
                num++;
                right = Math.min(right,intervals[i][1]);
            }else {
                right = intervals[i][1];
            }
        }
        return num;
    }
    // leetcode 452.用最少数量的箭引爆气球
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,Comparator.comparing(a -> a[0]));
        int n = points.length;
        if(n == 1) return 1;
        int num = 0;
        int left = points[0][0];
        int right = points[0][1];
        // 统计的是[当前位置之前的区域是否射箭]
        for(int i = 1;i < n;i++){
            int start1 = left;
            int end1 = right;
            int start2 = points[i][0];
            int end2 = points[i][1];
            // 存在重叠
            if(end1 >= start2){
                // 获取重叠部分
                left = Math.max(start1,start2);
                right = Math.min(end1,end2);
            }else {
                num++;
                left = points[i][0];
                right = points[i][1];
            }
            // 如果此时为最后一个区域必须发射
            if(i == n - 1) num++;
        }
        return num;
    }
}


















